// 筛法求约束和
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16714856.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/sieve/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000001;
int cnt;
int prime[MAXN];
bool visited[MAXN];
// g[i] 表示 i 的最小质因子的 1+p^1+...+p^k
int g[MAXN];
//f[i] 表示 i 的约数和
int f[MAXN];

// 试除法求约数和
int sum1(int n)
{
    if(n < 1) return 0;
    int ans = 1;
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            int p = 1;
            int count = 1;
            // count = 1+p^1+...+p^k
            while(n % i == 0)
            {
                p *= i;
                count += p;
                n /= i;
            }
            ans *= count;
        }
    }
    if(n > 1) ans *= (1 + n);
    return ans;
}

// 筛法求约数和
void sum2(int n)
{
    g[1] = f[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(!visited[i])
        {
            prime[++cnt] = i;
            g[i] = f[i] = i + 1;
        }
        for(int j = 1; 1LL * i * prime[j] <= n; ++j)
        {
            int m = i * prime[j];
            visited[m] = true;
            if(i % prime[j] == 0)
            {
                g[m] = g[i] * prime[j] + 1;
                f[m] = f[i] / g[i] * g[m];
                break;
            }
            else
            {
                g[m] = prime[j] + 1;
                f[m] = f[i] * g[m];
            }
        }
    }
}

int main()
{
    srand(time(nullptr));
    int testTime = 100000;
    sum2(MAXN - 1);
    for(int i = 0; i < testTime; ++i)
    {
        // 生成随机数据进行验证
        int n = rand() % MAXN;
        if(sum1(n) != f[n]) cout << "出错了！" << endl;
    }

    return 0;
}